package cn.whdream.datastructure.sort;

/**
 * 
 *插入排序
 */
public class insertSortDemo {
	public static void main(String[] args) {
		int arr[] = {101,34,-1,119,1,-64};
		insertSort(arr);
	}
	
	public static void insertSort(int[] arr) {
		int exchangeVal;
		int insertIndex;
		for (int i = 1; i < arr.length; i++) {
			exchangeVal = arr[i];//34 第一轮
			insertIndex = i-1;
			System.out.printf("index = %d val =%d \n",insertIndex,exchangeVal);
			//第一轮 相当于 判断 arr[1] < arr[0]
			while (insertIndex >= 0 && exchangeVal < arr[insertIndex]) {
				//第一轮： 把 101赋值到 arr[1]
				arr[insertIndex + 1] = arr[insertIndex];
				//放置到当前位置，直接实现前后的位置交换，也是可以的；但是，意味着执行更多无用的赋值交换操作
				//arr[insertIndex] = exchangeVal;
				//坐标回退
				insertIndex--;
			}
			//+1可以抵消上一次 while -- 后的后果，同时初始值是相差为1的 i和 insertIndex,+1可以使得 没有走循环的情况，赋值只赋到 自己原来的位置
			arr[insertIndex+1] = exchangeVal;
		}
		print(arr);
	}

	private static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
}
